#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 3e5+10;

int lz[N<<2],mn[N<<2],f[N<<2],g[N<<2],a[N],p[N];
int n,m;
ll ans;

void pushdown(int o,int l,int r){
	if(lz[o]){
		mn[o<<1] += lz[o]; mn[o<<1|1] += lz[o];
		lz[o<<1] += lz[o]; lz[o<<1|1] += lz[o];
		lz[o] = 0;
	}
}

void pushup(int o,int l,int r){
	mn[o] = min(mn[o<<1],mn[o<<1|1]);
	f[o] = f[o<<1] * (mn[o] == mn[o<<1]) + f[o<<1|1] * (mn[o] == mn[o<<1|1]);
	g[o] = g[o<<1] * (mn[o] == mn[o<<1]) + f[o<<1] * (mn[o] + 1 == mn[o<<1]) + g[o<<1|1] * (mn[o] == mn[o<<1|1]) + f[o<<1|1] * (mn[o] + 1 == mn[o<<1|1]);
}

void build(int o = 1,int l = 1,int r = n){
	if(l == r) return f[o] = 1,void();
	int mid = l + r>>1;
	build(o<<1,l,mid); build(o<<1|1,mid+1,r);
}

void upd(int xl,int xr,int v,int o = 1,int l = 1,int r = n){
	if(xl == l && xr == r){
		lz[o] += v; mn[o] += v;
		return;
	}
	int mid = l+r>>1;
	pushdown(o,l,r);
	if(xr <= mid) upd(xl,xr,v,o<<1,l,mid);
	else if(xl > mid) upd(xl,xr,v,o<<1|1,mid+1,r);
	else upd(xl,mid,v,o<<1,l,mid) , upd(mid+1,xr,v,o<<1|1,mid+1,r);
	pushup(o,l,r);
}

int query(int xl,int xr,int o = 1,int l = 1,int r = n){
	if(xl == l && xr == r)
		return f[o] * (mn[o] <= 2) + g[o] * (mn[o] <= 1);
	int mid = l+r>>1; pushdown(o,l,r);
	if(xr <= mid) return query(xl,xr,o<<1,l,mid);
	else if(xl > mid) return query(xl,xr,o<<1|1,mid+1,r);
	else return query(xl,mid,o<<1,l,mid) + query(mid+1,xr,o<<1|1,mid+1,r);
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in;
	for(int i = 1;i <= n;i++) a[i] = in,p[a[i]] = i;
	build();
	for(int i = 1;i <= n;i++){
	    int x = a[p[i]-1],y = a[p[i]+1];
		upd(1,i,1);
		if(x < i && x) upd(1,x,-1);
		if(y < i && y) upd(1,y,-1);
		if(i > 1) ans += query(1,i-1);
	}
	printf("%lld\n",ans);
	return 0;
}

